#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
int M = 0, C = 0;

void HeapSort_build(int A[], int L, int R){
    int x = A[L];
    int i = L;
    while(1){
        int j = 2 * i;
        if (j > R){
            break;
        }
        C++;
        if ((j < R) && (A[j+1] <= A[j])){
            j = j + 1;
        }
        C++;
        if (x <= A[j]){
            break;
        }
        M++;
        A[i] = A[j];
        i = j;
    }
    M++;
    A[i] = x;

}

void HeapSort(int A[], int n ){
    C = 0, M = 0;
    int L,R;
    L = floor((n-1)/2);
    while(L >= 0){
        HeapSort_build(A,L,n-1);
        L--;
    }
    R = n - 1;
    while(R > 0){
        M+=3;
        swap(A[0], A[R]);
        R--;
        HeapSort_build(A,0,R);
    }

}

void IncMas(int a[], int n){
    for (int i = 0; i<n; i++){
        a[i] = i+1;
    }
}

void DecMas(int a[], int n){
    for (int i = 0; i<n; i++){
        a[i] = n -i;
    }
}

void PrintMas(int a[], int n){
    for (int i = 0; i<n; i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

void RandMas(int a[], int n){
    for (int i = 0; i<n; i++){
        a[i] = rand()%10+1;
    }
}


int main(){
    srand(time(NULL));
    int n = 100;
    int *a;
    a = (int *)malloc(sizeof(int)*n);
    cout << "n" << setw(30) << "HeapSort (Mф + Cф)" << endl;
    cout << setw(10) << "inc" << setw(10) << "dec" << setw(10) << "rand" << endl;
    //100
    IncMas(a,n);
    HeapSort(a,n);
    int inc = M+C;
    DecMas(a,n);
    HeapSort(a,n);
    int dec = M+C;
    RandMas(a,n);
    HeapSort(a,n);
    int rand = M+C;
    cout << n << setw(8) << inc << setw(9) << dec << setw(9) << rand << endl;
    delete a;
    
    //200
    n = 200;
    a = (int *)malloc(sizeof(int)*n);
    IncMas(a,n);
    HeapSort(a,n);
    inc = M+C;
    DecMas(a,n);
    HeapSort(a,n);
    dec = M+C;
    RandMas(a,n);
    HeapSort(a,n);
    rand = M+C;
    cout << n << setw(8) << inc << setw(9) << dec << setw(9) << rand << endl;
    delete a;
    
    //300
    n = 300;
    a = (int *)malloc(sizeof(int)*n);
    IncMas(a,n);
    HeapSort(a,n);
    inc = M+C;
    DecMas(a,n);
    HeapSort(a,n);
    dec = M+C;
    RandMas(a,n);
    HeapSort(a,n);
    rand = M+C;
    cout << n << setw(8) << inc << setw(9) << dec << setw(9) << rand << endl;
    delete a;
    
    //400
    n = 400;
    a = (int *)malloc(sizeof(int)*n);
    IncMas(a,n);
    HeapSort(a,n);
    inc = M+C;
    DecMas(a,n);
    HeapSort(a,n);
    dec = M+C;
    RandMas(a,n);
    HeapSort(a,n);
    rand = M+C;
    cout << n << setw(8) << inc << setw(9) << dec << setw(9) << rand << endl;
    delete a;
    
    //500
    n = 500;
    a = (int *)malloc(sizeof(int)*n);
    IncMas(a,n);
    HeapSort(a,n);
    inc = M+C;
    DecMas(a,n);
    HeapSort(a,n);
    dec = M+C;
    RandMas(a,n);
    HeapSort(a,n);
    rand = M+C;
    cout << n << setw(8) << inc << setw(9) << dec << setw(9) << rand << endl;
    delete a;
}
